package 数据结构OJ;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/6/25 15:01
 * @Description:
 */
public class 二叉树中和为某一值的路径 {
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        //创建一个pathList接受所有的路径，
        //新建一个Stack来保存路径中的值，如果符合要求，就保存起来，如果不符合要求，就会从栈中删除
        ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
        Stack<Integer> path = new Stack<Integer>();
        //递归调用
        innercall(root, target, pathList, path);
        return pathList;
    }

    private void innercall(TreeNode root, int target,
                           ArrayList<ArrayList<Integer>> pathList,
                           Stack<Integer> path) {
        if (root == null)
            return;
        //判断是否为叶子节点，如果是，判断叶子节点是否等于需要的值（每次调用都会减去当前节点的值，
        // 所以如果路径为需要的路径，到叶子节点时，target就会等于叶子节点值）
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                //从栈path中将值存入arraylist
                for (int i : path) {
                    list.add(i);
                }
                //此时叶子节点还未存入stack，所以需要单独存一次
                list.add(root.val);
                //将本条path当做pathList的参数存起来
                pathList.add(list);
            }
        } else {
            //不是叶子节点，就将当前节点值入栈，然后前序遍历，
            path.push(root.val);
            innercall(root.left, target - root.val, pathList, path);
            innercall(root.right, target - root.val, pathList, path);
            path.pop();
        }
    }
}